//
//      Author: Alexandros Sigalas
//
//      This program is free software; you can redistribute it and/or modify
//      it under the terms of the GNU General Public License as published by
//      the Free Software Foundation; either version 2 of the License, or
//      (at your option) any later version.
//      
//      This program is distributed in the hope that it will be useful,
//      but WITHOUT ANY WARRANTY; without even the implied warranty of
//      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//      GNU General Public License for more details.
//      
//      You should have received a copy of the GNU General Public License
//      along with this program; if not, write to the Free Software
//      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
//      MA 02110-1301, USA.

#include <stdlib.h>
#include <assert.h>
#include "islands.h"
#include "mesh.h"
#include "math.h"
#include "globals.h"
#include "polygon.h"

uint me_find_islands(mesh me, island *islands, double thresh)
{
    assert(me);
    uint nfaces= me->last_f;
    vec normals[nfaces];
    int times_used[nfaces];
    facelist adjascent_faces[nfaces];
    *islands= (island)calloc(nfaces, sizeof(struct M_FaceIsland));
    uint i;
    mface f;
    for (i=0; i < nfaces; i++){
        times_used[i]= 0;
        f= me->faces + i;
        mf_normal(f, normals + i);
        adjascent_faces[i]= mf_adjascent_faces(f);
    }
    
    facelist near_faces;
    island isl;
    uint idx_a, idx_b, j, count= 0;
    mface f_a, f_b;
    int expanding, no_more_islands;
    
    while (1)
    {
        no_more_islands= 1;
        for (i=0; i < nfaces; i++)
        {
            if (times_used[i] == 0)
            {
                isl= islands[count++];
                island_add_face(isl, me->faces + i);
                no_more_islands= 0;
                times_used[i]++;
                break;
            }
        }
        
        if (no_more_islands)
            break;
        
        expanding= 1;
        while (expanding)
        {
            expanding= 0;
            for (i=0; i < isl->last_f; i++)
            {
                f_a= isl->faces[i];
                idx_a= f_a - me->faces;
                if (times_used[idx_a] == 1)
                {
                    times_used[idx_a]++;
                    near_faces= adjascent_faces[idx_a];
                    for (j=0; j < near_faces->last; j++)
                    {
                        f_b= near_faces->faces[i];
                        idx_b= f_b - me->faces;
                        if (times_used[idx_b] == 0)
                        {
                            expanding= 1;
                            if ((f_b->mat == f_a->mat) && 
                                (v_dot( normals + idx_a, normals + idx_b) < thresh))
                            {
                                times_used[idx_b]= 1;
                                island_add_face(isl, f_b);
    }   }   }   }   }   }   }
    return count;
}

void island_add_face(island isl, mface f)
{
    assert(f);
    assert(isl);
    if (!isl->faces){
        isl->size_f= 10;
        isl->faces= (mface*)malloc(10*sizeof(mface));
        mf_normal(f, &isl->normal);
        isl->mat= f->mat;
        isl->size_e= 20;
        isl->edges= (medge*)malloc(20*sizeof(medge));
        isl->edges[0]= f->edges[0];
        isl->edges[1]= f->edges[1];
        isl->edges[2]= f->edges[2];
        isl->last_e= 3;
        isl->faces[0]= f;
        isl->last_f= 1;
        return;
    }
    else if (isl->last_f == isl->size_f){
        isl->size_f*= 2;
        isl->faces= (mface*)realloc(isl->faces, isl->size_f*sizeof(mface));
        assert(isl->faces);
    }
    isl->faces[isl->last_f++]= f;
    
    if (isl->last_e + 2 == isl->size_e){
        isl->size_e= (isl->size_e * 2 + 2);
        isl->edges= (medge*)realloc(isl->edges, isl->size_e*sizeof(medge));
    }
    
    //// keep only unique edges
    uint i, j, count=0;
    medge tmp[isl->size_e];
    int valid[3]= {1, 1, 1};
    medge e;
    
    for(i=0; i < isl->last_e; i++){
        e= isl->edges[i];
        for (j=0; j < 3; j++){
            if (f->edges[j] == e){
                valid[j]= 0;
                e= NULL;
                break;
            }
        }
        if (e)
            tmp[count++]= e;
    }
    for(i=0; i < count; i++){
        isl->edges[i]= tmp[i];
    }
    isl->last_e= count;
    for(i=0; i < 3; i++){
        if (valid[i])
            isl->edges[isl->last_e++]= f->edges[i];
    }
}
polygon island_to_poly(island isl, uint cop_id)
{
    assert(isl);
    uint count= isl->last_e;
    uint edges_left= count;
    mvert points[2 * count + 2];
    mvert *head= points + count;
    mvert *tail= head - 1;
    uint pcount= 0;
    uint i;
    int used[count];
    for (i=0; i < count; i++)
        used[i]= 0;
    int expanding;
    medge e;
    polygon pl= NULL;
    polylist loops= NULL;
    while(edges_left){
        expanding= 1;
        count--;
        e= isl->edges[count];
        used[count]= 1;
        *head= e->v1;
        *tail= e->v0;
        while (expanding && edges_left){
            expanding= 0;
            for (i=0; i < count; i++){
                e= isl->edges[i];
                if (used[i])
                    continue;

                expanding= 1;    
                if (*head == e->v0){
                    head++;
                    *head= e->v1;
                }
                else if (*head == e->v1){
                    head++;
                    *head= e->v0;
                }
                else if (*tail == e->v0){
                    tail--;
                    *tail= e->v1;
                }
                else if (*tail == e->v1){
                    tail++;
                    *tail= e->v0;
                }
                else{
                    expanding= 0;
                }
                
                if (expanding){
                    used[i]= 1;
                    edges_left--;
                    break;
                }
            }
            pcount= head - tail;
            if (pcount > 3){
                pl= pl_init(pcount);
                for(i=0; i < pcount; i++)
                    pl_append_point(&pl, &points[i]->co);
                pll_append(&loops, pl);
                pl= NULL; 
            }
        }
    }
    pll_sort_by_area(loops);
    pl= pll_pop(loops);
    vec no;
    pl_normal(pl, &no);
    if (v_dot(&no, &isl->normal) < 0.0)
        pl_reverse(pl);
    enum PL_Order ord= pl_order(pl);
    if (loops->last){
        polygon hole;
        for (i=0; i < loops->last; i++){
            hole= loops->polys[i];
            if (pl_order(hole) != ord)
                pl_reverse(hole);
            hole->attr|= HOLE;
            pll_append(&pl->holes, hole);
        }
    }
    pl->props.coplanar_id= cop_id;
    return pl;
}

void island_kill(island *isl_pt)
{
    assert(isl_pt);
    island isl= *isl_pt;
    if (isl){
        if (isl->edges)
            free(isl->edges);
        if (isl->faces)
            free(isl->faces);
    }
    *isl_pt= NULL;
}
        
